package com.ruijixiang.leetcode.weekly.leetcode2024.leetcode20240908;

import java.util.Arrays;

public class leetcode3281 {
    // 二分法，这道题有点难
    public int maxPossibleScore(int[] start,int d){
        Arrays.sort(start);
        int n=start.length;
        int left=0;
        int right=(start[n-1]+d-start[0])/(n-1)+1;
        while(left+1<right){
            int mid=(left+right)>>>1;
            if(check(start,d,mid)){
                left=mid;
            }else{
                right=mid;
            }
        }
        return left;
    }

    private boolean check(int[] start,int d,int score){
        long x=Long.MIN_VALUE;
        for(int s : start){
            x=Math.max(x+score,s);// 必须>=区间左端点
            if(x>s+d){
                return false;
            }
        }
        return true;
    }
}
